package queue

/*
无锁队列测试
http://stackoverflow.com/questions/12291949/why-my-golang-lock-free-queue-always-stuck-there?t=1449926285392
http://www.cnblogs.com/niniwzw/archive/2012/10/28/2743296.html
https://github.com/scryner/lfreequeue
*/

import (
	"runtime"
	"sync/atomic"
	"unsafe"
)

// lock free queue
type Queue struct {
	head   unsafe.Pointer
	tail   unsafe.Pointer
	notice chan bool
	counts int
}

// one node in queue
type Node struct {
	val  interface{}
	next unsafe.Pointer
}

func (q *Queue) Enqueue(val interface{}) {
	newValue := unsafe.Pointer(&Node{val: val, next: nil})
	var tail, next unsafe.Pointer
	for {
		tail = q.tail
		next = ((*Node)(tail)).next
		if next != nil {
			atomic.CompareAndSwapPointer(&(q.tail), tail, next)
		} else if atomic.CompareAndSwapPointer(&((*Node)(tail).next), nil, newValue) {
			break
		}
		runtime.Gosched()
	}
	select {
	case q.notice <- true:
	default:
	}
	q.counts++
}

func (q *Queue) Dequeue() (val interface{}, success bool) {
	var head, tail, next unsafe.Pointer
	for {
		head = q.head
		tail = q.tail
		next = ((*Node)(head)).next
		if head == tail {
			if next == nil {
				return nil, false
			} else {
				atomic.CompareAndSwapPointer(&(q.tail), tail, next)
			}
		} else {
			val = ((*Node)(next)).val
			if atomic.CompareAndSwapPointer(&(q.head), head, next) {
				q.counts--
				return val, true
			}
		}
		runtime.Gosched()
	}
	// return nil, false
}

func (q *Queue) MustDequeue() interface{} {

	for {
		if val, ok := q.Dequeue(); ok {
			return val
		}
		<-q.notice
	}
}

func (q *Queue) Size() int {
	return q.counts
}

func (q *Queue) Empty() {
	var head, tail, next unsafe.Pointer
	for {
		head = q.head
		tail = q.tail
		next = ((*Node)(head)).next
		if head == tail {
			if next == nil {
				return
			} else {
				atomic.CompareAndSwapPointer(&(q.tail), tail, next)
			}
		} else {
			if atomic.CompareAndSwapPointer(&(q.head), head, next) {
				q.counts--
			}
		}
		runtime.Gosched()
	}
}

func NewQueue() *Queue {
	node := unsafe.Pointer(new(Node))
	return &Queue{
		head:   node,
		tail:   node,
		notice: make(chan bool),
	}
}
